package main.leetcode.primary.from001to100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 47.全排列II
 *
 * <p>给定一个可包含重复数字的序列，返回所有不重复的全排列。
 *
 * <p>示例:输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex47 {
  public static void main(String[] args) {
    System.out.println(new ex47().permuteUnique(new int[] {1, 1, 2}));
  }

  // 回溯
  public List<List<Integer>> permuteUnique(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    if (n == 0) return res;
    boolean[] isUsed = new boolean[n]; // 标记是否被使用过（用于状态重置
    Arrays.sort(nums);
    dfs(nums, n, 0, isUsed, new ArrayList<>(), res);
    return res;
  }

  private void dfs(
      int[] nums, int n, int i, boolean[] isUsed, List<Integer> path, List<List<Integer>> res) {
    if (i == n) {
      res.add(new ArrayList<>(path)); // 拷贝
      return;
    }
    for (int j = 0; j < n; j++) {
      if (isUsed[j]
          || j > 0
              && nums[j] == nums[j - 1] // 重复的值（因为已排序所以必定相邻
              && !isUsed[j - 1]) // 选用!isUsed而不选用isUsed（两者都可以，区别仅在于保留的是相同元素的顺序索引，还是倒序索引，但是前者剪枝更彻底）
      continue;
      path.add(nums[j]);
      isUsed[j] = true;
      dfs(nums, n, i + 1, isUsed, path, res); // 放下一个数
      isUsed[j] = false; // 状态重置
      path.remove(path.size() - 1); // 状态重置
    }
  }
}
